package com.lw.leetcode.sort;


import java.util.Arrays;

/**
 * 快速排序
 *
 * @Author liw
 * @Version 1.0
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {1,10, 11, 5, 0, 5, 5, 5, 3, 6, 2, 4};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int st, int end) {
        if (end <= st) {
            return;
        }
        int index = st;
        int count = 0;
        int length = end - st;
        int limit = end;
        while (count < length) {
            if (arr[index + 1] < arr[index]) {
                int item = arr[index + 1];
                arr[index + 1] = arr[index];
                arr[index] = item;
                index++;
            } else if (arr[index + 1] > arr[index]) {
                int item = arr[index + 1];
                arr[index + 1] = arr[limit];
                arr[limit] = item;
                limit--;
            } else {
                index++;
            }
            count++;
        }
        quickSort(arr, st, index - 1);
        quickSort(arr, index + 1, end);
    }

}
